package com.sujeet.euler;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class LargestPrimeFactor {

	public static void main(String[] args) throws Exception {
		long test = 600851475143L;
		long divisorLimit = Math.round(Math.sqrt(test)); // should test from only square root of the number
		int numberOfGroups = 300;
		long groupSize = divisorLimit / numberOfGroups;
		ExecutorService exec = Executors.newFixedThreadPool(numberOfGroups);
		SharedDecisionHelper sharedDecisionHelper = new SharedDecisionHelper();
		try {
			for (int i = numberOfGroups; i >= 1; i--) {
				Runnable task = createTask(i, groupSize, sharedDecisionHelper, test);
				exec.submit(task);
			}
			exec.shutdown();
			exec.awaitTermination(1, TimeUnit.SECONDS);
		} finally {
			System.out.println("\nLargest Prime Factor:");
			System.out.println(sharedDecisionHelper.getaPrimeFactor());
		}
	}

	private static Runnable createTask(final int myGroupId,
			final long groupSize,
			final SharedDecisionHelper sharedDecisionHelper,
			final long testNumber) {

		Runnable task = new Runnable() {
			long lowerLimit = (myGroupId - 1) * groupSize + 1;
			long higherLimit = myGroupId * groupSize;

			@Override
			public void run() {
				System.out.println("\n" + Thread.currentThread().getId()
						+ ":myGroupId:" + myGroupId + ": lowerLimit:"
						+ lowerLimit + ": higherLimit:" + higherLimit);
				if (lowerLimit == 1) {
					lowerLimit = 3; // do not test with 1 and 2
				}
				while (true) {
					if (sharedDecisionHelper.getGroupId() < myGroupId) {
						if (higherLimit >= lowerLimit) {
							if (testNumber % higherLimit == 0) {
								if (isPrime(higherLimit)) {
									synchronized (sharedDecisionHelper) {
										if (sharedDecisionHelper.getGroupId() < myGroupId) {
											sharedDecisionHelper.inform(
													myGroupId, higherLimit);
										} else {
											// never comes here - highest group adds - lower groups do not get chance
											System.out
													.println("\n Could not add "
															+ higherLimit
															+ " as a bigger value "
															+ sharedDecisionHelper
																	.getGroupId()
															+ " already present");
										}
									}
									break;
								}
							}
						} else {
							break;
						}
						--higherLimit;
					} else {
						System.out.println("\n" + Thread.currentThread().getId()
								+ ":myGroupId:" + myGroupId + " dying");
						break;
					}
				}
			}
		};
		return task;
	}

	public static boolean isPrime(long n) {
		System.out.println("\nchecking primality for " + n);
		// divisible by 2
		if (n % 2 == 0)
			return false;
		// divisible by 3
		if (n % 3 == 0)
			return false;
		// divisible by numbers of form 6k+1 or 6k-1
		System.out.println("\nchecking with ");
		for (int i = 4; i <= Math.sqrt(n); i++) {
			// of form 6k+1
			if (((i - 1) % 6 == 0) || ((i + 1) % 6 == 0)) {
				System.out.print(", " + i);
				if (n % i == 0)
					return false;
			}
		}
		return true;
	}

	private static class SharedDecisionHelper {
		private int groupId = -1;
		private long aPrimeFactor = 0;

		public int getGroupId() {
			return groupId;
		}

		public long getaPrimeFactor() {
			return aPrimeFactor;
		}

		public void inform(int groupId, long aPrimeFactor) {
			this.groupId = groupId;
			this.aPrimeFactor = aPrimeFactor;
			System.out.println("\n Incoming from thread "
					+ Thread.currentThread().getId() + ":" + this);
		}

		public String toString() {
			return "groupId=" + groupId + " aPrimeFactor=" + aPrimeFactor;
		}
	}

}
